package com.dexter.year2023.charpter1_linkedlist.level2.topic2_5删除元素;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;
import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.printLinkedList;

/**
 * LeetCode 19. 删除链表的倒数第N个结点
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
 * <p>
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 * <p>
 * 提示：
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 * <p>
 * 进阶：你能尝试使用一趟扫描实现吗？
 *
 * @author Dexter
 */
public class Demo2RemoveNthFromEnd {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        Node head = initLinkedList(a);
        int n = 2;
        // 方法选择
        int testMethod = 1;
        switch (testMethod) {
            case 1:
                // 本节方法，与2-4中旋转链表的思路一致，slow需要走到“目标位置”的前一个 （遍历一次，符合进阶要求）
                head = removeNthFromEndByTwoPoints(head, n);
                break;
            case 2:
                // 还有一个计算长度的方法，需要遍历两次（不推荐）
                head = removeNthFromEndByLength(head, n);
                break;
            default:
                System.out.println("测试方法超出范围");
                break;
        }
        printLinkedList(head);
    }

    private static Node removeNthFromEndByTwoPoints(Node head, int n) {
        // 涉及头结点的删除，虚拟结点
        Node dummy = new Node(-1);
        dummy.next = head;
        // 定义快慢指针
        Node slow = dummy, fast = head;
        while (fast != null && n > 0) {
            fast = fast.next;
            n--;
        }
        // 一起走，注意slow是从dummy过来的
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

    private static Node removeNthFromEndByLength(Node head, int n) {
        // 虚拟结点
        Node dummy = new Node(-1);
        dummy.next = head;
        // 计算长度
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        // 需要走的步数是 len - n + 1
        Node cur = dummy;
        for (int i = 1; i < len - n + 1; i++) {
            cur = cur.next;
        }
        // 删除
        cur.next = cur.next.next;
        return dummy.next;
    }
}
